<!--
 * @Description: 
 * @Autor: wangxin
 * @Date: 2020-06-13 22:56:31
 * @LastEditTime: 2020-06-13 23:51:35
-->
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /*
       * @Description: 分离链接
       * @Autor: wangxin
       * @Date: 2020-06-13 22:28:12
       * @LastEditTime: 2020-06-13 22:56:05
       */
      class Node {
        constructor(element) {
          this.element = element
          this.next = null
        }
      }
      class LinkedList {
        constructor() {
          this.count = 0
          this.head = null
        }

        /**
         * 向链表尾部添加新元素
         */
        push(element) {
          const node = new Node(element)
          let current
          if (this.head == null) {
            this.head = node
          } else {
            current = this.head
            // 获得最后一项
            while (current.next != null) {
              current = current.next
            }
            // 将next赋为新元素，建立链接
            current.next = node
          }

          this.count++
        }
        /**
         * 循环迭代链表直到目标位置
         */
        getElementAt(index) {
          if (index < 0 || index >= this.count) {
            return undefined
          }
          let current = this.head
          for (let i = 0; i < index; i++) {
            current = current.next
          }
          return current
        }
        /**
         * 从链表中特定位置移除一个元素
         */
        removeAt(index) {
          // 检查越界值
          if (index < 0 || index >= this.count) {
            return undefined
          }
          let current = this.head
          // 移除第一项
          if (index === 0) {
            this.head = current.next
          } else {
            const previous = this.getElementAt(index - 1)
            // 需要被移除的项
            current = previous.next
            // 跳过current，从而移除它
            previous.next = current.next
          }
          this.count--
          return current.element
        }
        /**
         * 在任意位置插入元素
         */
        insert(element, index) {
          // 检查越界值
          if (index < 0 || index > this.count) {
            return false
          }
          const node = new Node(element)

          // 在第一个位置插入元素
          if (index === 0) {
            const current = this.head
            node.next = current
            this.head = node
          } else {
            // 插入新元素的前一个元素
            const previous = this.getElementAt(index - 1)
            // 插入新元素的后一个元素
            const current = previous.next
            node.next = current
            previous.next = node
          }
          this.count++
          return true
        }
        /**
         * 返回一个元素的位置，没有找到返回-1
         */
        indexOf(element) {
          let current = this.head

          for (let i = 0; i < this.count; i++) {
            if (current.element == element) {
              return i
            }
            current = current.next
          }
          // 没有找到
          return -1
        }
        /**
         * 把链表转换成一个字符串
         */
        toString() {
          if (this.head == null) {
            return ''
          }
          let objString = `${this.head.element}`
          let current = this.head.next
          for (let i = 1; i < this.count; i++) {
            objString = `${objString},${current.element}`
            current = current.next
          }
          return objString
        }
        /**
         * 从链表中移除元素
         */
        remove(element) {
          const index = this.indexOf(element)
          return this.removeAt(index)
        }
        /**
         * 判断链表是否有元素
         */
        isEmpty() {
          return this.count === 0
        }
        /**
         * 返回链表的长度
         */
        size() {
          return this.count
        }
        /**
         * 返回链表的头部元素
         */
        getHead() {
          return this.head
        }
      }
      class ValuePair {
        constructor(key, value) {
          this.key = key
          this.value = value
        }
        toString() {
          return `[${this.key}:${this.value}]`
        }
      }

      class HashTableSeparateChaining {
        constructor(toStrFn = this.defauiltToString) {
          this.toStrFn = toStrFn
          this.table = {}
        }

        defauiltToString(item) {
          if (item === null) {
            return 'NULL'
          } else if (item === undefined) {
            return 'UNDEFINED'
          } else if (typeof item === 'string' || item instanceof String) {
            return `${item}`
          }
          return item.toString()
        }

        loseHashCode(key) {
          if (typeof key === 'number') {
            return key
          }
          const tableKey = this.toStrFn(key)
          let hash = 0
          for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i)
          }
          return hash % 37
        }

        hashCode(key) {
          return this.loseHashCode(key)
        }

        size() {
          return Object.keys(this.table).length
        }

        isEmpty() {
          return this.size() === 0
        }

        toString() {
          if (this.isEmpty()) {
            return ''
          }
          const keys = Object.keys(this.table)
          let objStrng = `{${keys[0]}--${this.table[keys[0]].toString()}}`
          for (let i = 1; i < keys.length; i++) {
            objStrng = `${objStrng},${keys[i]}--${this.table[
              keys[i]
            ].toString()}`
          }
          return objStrng
        }

        put(key, value) {
          if (key != null && value != null) {
            const position = this.hashCode(key)
            if (this.table[position] == null) {
              this.table[position] = new LinkedList()
            }
            this.table[position].push(new ValuePair(key, value))
            return true
          }
          return false
        }

        get(key) {
          const position = this.hashCode(key)
          const linkedList = this.table[position]
          if (linkedList != null && !linkedList.isEmpty()) {
            let current = linkedList.getHead()
            while (current != null) {
              if (current.element.key === key) {
                return current.element.value
              }
              current = current.next
            }
          }
          return undefined
        }

        remove(key) {
          const position = this.hashCode(key)
          const linkedList = this.table[position]
          if (linkedList != null && !linkedList.isEmpty()) {
            let current = linkedList.getHead()
            while (current != null) {
              if (current.element.key === key) {
                linkedList.remove(current.element)
                if (linkedList.isEmpty()) {
                  delete this.table[position]
                }
                return true
              }
              current = current.next
            }
          }
          return false
        }
      }

      const hash = new HashTableSeparateChaining()
      hash.put('Nathan', 'Nathan.com')
      hash.put('Sargeras', 'Sargeras.com')

      hash.put('Jack', 'Jack.com')
      hash.put('Athelstan', 'Athelstan.com')

      hash.put('Jamie', 'Jamie.com')
      hash.put('Sue', 'Sue.com')
      console.log(hash.toString())
    </script>
  </body>
</html>
